/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 100;
//意义见wiki
ll fa[maxn], son[maxn], dep[maxn], siz[maxn];
ll top[maxn], dfn[maxn], rnk[maxn];
ll cnt;             //剖分后的编号
vector<ll> p[maxn]; //边

//重链剖分
void dfs1(ll u)
{ //预处理出fa,son,dep,siz
    son[u] = -1;
    siz[u] = 1;
    ll len = p[u].size();
    for (ll i = 0; i < len; i++)
    {
        ll v = p[u][i];
        if (dep[v] > 0)
            continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        //更新重子节点
        if (son[u] == -1 || siz[son[u]] < siz[v])
        {
            son[u] = v;
        }
    }
    return;
}
void dfs2(ll u, ll f)
{ //更新top,dfn,rnk
    top[u] = f;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    if (son[u] == -1)
        return;
    dfs2(son[u], f);
    ll len = p[u].size();
    for (ll i = 0; i < len; i++)
    {
        ll v = p[u][i];
        if (v == son[u] || v == fa[u])
            continue;
        dfs2(v, v);
    }
    return;
}
//你倒是打开一个编辑器表示一下对老师的尊重
//求LCA
ll LCA(ll u, ll v)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] > dep[top[v]])
        {
            u = fa[top[u]];
        }
        else
            v = fa[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}

int main()
{
    IOS;

    getchar();
    getchar();
    return 0;
}
